package datastruct.tree.binarytree.threadedbinarytree;

import lombok.Data;

/**
 * @program: DataStructuresAndAlgorithms
 * @description: 线索二叉树
 * @author: zhang
 * @create: 2020-03-11 10:38
 */
public class ThreadedBinaryDemo {
    public static void main(String[] args) {

    }

}

//实现了线索化功能的二叉树
@Data
class ThreadedBinaryTree{
    private HeroNode root;

    //创建要给指向当天结点的前驱结点的指针
    //在递归进行线索化时，pre总是保留前一个结点
    private HeroNode pre =null;

    //遍历线索二叉树
    public void threadedList(){
        //定义一个变量，存储当前遍历的节点，从root开始
        HeroNode node = root;
        while (node != null){
            //循环的找到leftType==1的结点，第一个找到就是
            //后面随着遍历而变化，因为leftType==1时，说明该结点时按照线索化
            //处理后的有效结点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            //打印当前这个结点
            System.out.println(node);
            //如果当前结点的有指针指向的是后继结点,就一直输出
            while (node.getRightType() == 1){
                //获取当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的节点
            node = node.getRight();
        }
    }

    //编写对二叉树进行中序线索化的方法、
    public void threadedNodes(HeroNode node){
        if (node == null){
            return;
        }

        //1.先线索化左子树
        threadedNodes(node.getLeft());
        //2.线索化当前结点
        //处理当前结点的前驱结点
        if (node.getLeft() == null){
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型，指向前驱结点
            node.setLeftType(1);
        }
        //处理后继结点
        if (pre != null && pre.getRight() == null){
            //让前驱结点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱结点的有指针类型
            pre.setLeftType(1);
        }
        //每处理一个结点后，pre指向当前结点
        pre = node;

        //3.后线索化右子树
        threadedNodes(node.getRight());
    }
    public void delNode(int no){
        if (root != null){
            if(no == root.getNo()){
                root = null;
            }else {
                root.delNode(no);
            }
        }else {
            System.out.println("您删除的是空树!!!");
        }
    }
    public void preOrder(){
        if (this.root != null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    public void infixOrder(){
        if (this.root != null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    public void postOrder(){
        if (this.root != null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public HeroNode preOrderSearch(int no){
        if (this.root != null){
            return this.root.preOrderSearch(no);
        }else {
            return null;
        }
    }
    public HeroNode infixOrderSearch(int no){
        if (this.root != null){
            return this.root.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    public HeroNode postOrderSearch(int no){
        if (this.root != null){
            return this.root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}
@Data
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    //1.如果leftType==0表示指向的是左子树，如果1则表示指向前驱结点
    //2.如果rightType==0 表示指向是右子树，如果1表示指向后继结点
    private int leftType;
    private int rightType;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }


    //删除节点
    public void delNode(int no){
        if (this.left != null && no == this.left.no){
            this.left = null;
            return;
        }
        if (this.right != null && no == this.right.no){
            this.right = null;
            return;
        }
        //递归左子树查找并删除
        if (this.left != null){
            this.left.delNode(no);
        }
        //递归右子树查找并删除
        if (this.right != null){
            this.right.delNode(no);
        }
    }
    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.left != null){
            this.left.preOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.preOrder();
        }
    }
    //后序遍历
    public void postOrder(){
        if (this.left != null){
            this.left.postOrder();
        }
        if (this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序遍历查找
    public HeroNode preOrderSearch(int no){
        System.out.println("进入前序查找~~~");
        if (this.no == no){
            return this;
        }
        HeroNode resNode = null;
        if (this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null){
            return resNode;
        }
        if (this.right != null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //中序遍历查找
    public HeroNode infixOrderSearch(int no){

        HeroNode resNode = null;
        if (this.left != null){
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null){
            return resNode;
        }
        System.out.println("进入中序查找~~~");
        if (this.no == no){
            return this;
        }
        if (this.right != null){
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }
    //后序遍历查找

    public HeroNode postOrderSearch(int no){

        HeroNode resNode = null;
        if (this.left != null){
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null){
            return resNode;
        }
        if (this.right != null){
            resNode = this.right.infixOrderSearch(no);
        }
        if (resNode != null){
            return resNode;
        }
        System.out.println("进入后序查找~~~");
        if (this.no == no){
            return this;
        }
        return null;
    }
}